package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/24 9:57
 */
public class 数组中第K个最大元素 {

    //0   1   2   3  4  5
    static class Heap{

        private int [] arr;
        private int size;
        private int capcity;

        public Heap(int capcity){
            arr = new int[capcity];
            this.capcity = capcity;
            this.size = 0;
        }

        public Heap(int[] arr) {
            this.arr = arr;
            this.capcity = arr.length;
            this.size = arr.length;
            adjust_down();
        }

        public void add(int val){
            arr[size++] = val;
        }

        //取出栈顶的数
        public int poll(){
            int poll = arr[0];
            swap(0, size -1);
            size--;
            down(0, size);
            return poll;
        }
        public boolean isEmpty(){
            return size == 0;
        }

        public void print(){
            for(int i = 0; i< size; i++){
                System.out.print(arr[i]+" ");
            }
            System.out.println();
        }

        //从头部开始比较，更前面的比较
        public void up(){
            for(int i = 0; i< size; i++){
                int idx = i;
                while(arr[idx] > arr[(idx-1)/2]){
                       swap(idx,(idx-1)/2);
                        idx = (idx - 1)/2;
                }
            }

        }
        //从头部比较，跟后面的比较
        public void down(int idx,int size){
            int left = 2 * idx + 1;
            while(left < size){
                int right = 2 * idx + 2;
                right = right <size? right : size-1;
                int lagerIndex = arr[left] > arr[right] ? left : right;
                int large = arr[left] > arr[right] ? arr[left] : arr[right];
                if(arr[idx] < large){
                    swap(idx,lagerIndex);
                }else{
                    break;
                }
                idx = lagerIndex;
                left = 2 * idx + 1;
            }
        }

        //调整为大根堆
        public void adjust_up(){
            //每次把第一个移动到最后一位，然后执行 up或者down函数
            for(int i = 0; i < size; i++){
                up();
            }
        }

        /**
         * 调整为大根堆 效率比sort好
         */
        public void adjust_down(){
            for(int i = size -1; i>=0; i--){
                down(i, size);
            }
        }

        //大根堆排序 从小到大
        public void sort(){
            //首个值替换到最后一位，然后down
            int lastIndex = size - 1;
            while(lastIndex > 0){
                swap(0,lastIndex);
                down(0,lastIndex);
                lastIndex--;
            }
        }


        public void swap(int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }

    public int findKthLargest(int[] nums, int k) {
        Heap heap = new Heap(nums);
        int temp =0;
        for(int i =0;i<k;i++){
            temp = heap.poll();
        }
        return temp;
    }

    public static void main(String[] args) {
        int [] arr={3,2,3,1,2,4,5,5,6};
        Heap heap = new Heap(arr);
        heap.print();
        heap.sort();
        heap.print();
        System.out.println();
        heap.adjust_down();
        while(!heap.isEmpty()){
            System.out.println(heap.poll());
        }
    }

}
